/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class code2 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //出口
        if(root == null) return null;

        //q/p是root
        if(root==q || root==p) return root;

        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);

        //p/q不是root
        if(left!=null && right!=null) {
            //pq在左右两侧
            return root;
        } else if(left != null){
            //都在左侧
            return left;
        } else {
            //都在右侧
            return right;
        }

    }

}
